lazy propagation 백준 10999번: 구간 합 구하기 2 구간의 길이가 최대 N이므로 구간에 존재하는 모든 노드를 바꾸려면 NlogN이 걸린다. 해당 구간에 존재하는 모든 노드를 업데이트하지 말고, 이 노드는 업데이트가 필요합니다! 라고 표시만 해놓고 나중에 방문할 때 업데이트를 해주면 어떨까? 딱 맞는 구간까지만 업데이트하고, 그 구간을 표시하는 노드의 left, right child에 표시를 해둔다. 나중에 그 child를 방문했을 때, 값을 ... lazy propagationSegment TreepscppSegment Tree 백준 12844번: XOR XOR 연산은 결합법칙과 교환법칙이 성립한다. 따라서 구간합 세그먼트 트리처럼 구성할 수 있다. lazy[node*2] ^= lazy[node] 해야하는데 +=을 써버렸다. 상위 노드만 연속으로 방문해서 자식 노드에 업데이트 해야하는 내용이 쌓일 수 있기 때문에 항상 0이라는 보장을 할 수 없다. 주의하도록 하자..!... lazy propagationSegment TreepscppSegment Tree 알고리즘 스터디 - 3주차 알고리즘 스터디 내용 및 회고 주제 Segment Tree(lazy propagation) 백준 10999번(lazy propagation을 이용한 문제) Segment Tree(lazy propagation) Segment Tree에서 구간 업데이트를 빠르게 하기 위해 적용한 lazy propagation에 대해 공부하였음. 컴퓨터구조에서 배운 캐시의 개념과 비슷하게 생각하였음. 참고 : ... Segment Treelazy propagationSegment Tree
백준 10999번: 구간 합 구하기 2 구간의 길이가 최대 N이므로 구간에 존재하는 모든 노드를 바꾸려면 NlogN이 걸린다. 해당 구간에 존재하는 모든 노드를 업데이트하지 말고, 이 노드는 업데이트가 필요합니다! 라고 표시만 해놓고 나중에 방문할 때 업데이트를 해주면 어떨까? 딱 맞는 구간까지만 업데이트하고, 그 구간을 표시하는 노드의 left, right child에 표시를 해둔다. 나중에 그 child를 방문했을 때, 값을 ... lazy propagationSegment TreepscppSegment Tree 백준 12844번: XOR XOR 연산은 결합법칙과 교환법칙이 성립한다. 따라서 구간합 세그먼트 트리처럼 구성할 수 있다. lazy[node*2] ^= lazy[node] 해야하는데 +=을 써버렸다. 상위 노드만 연속으로 방문해서 자식 노드에 업데이트 해야하는 내용이 쌓일 수 있기 때문에 항상 0이라는 보장을 할 수 없다. 주의하도록 하자..!... lazy propagationSegment TreepscppSegment Tree 알고리즘 스터디 - 3주차 알고리즘 스터디 내용 및 회고 주제 Segment Tree(lazy propagation) 백준 10999번(lazy propagation을 이용한 문제) Segment Tree(lazy propagation) Segment Tree에서 구간 업데이트를 빠르게 하기 위해 적용한 lazy propagation에 대해 공부하였음. 컴퓨터구조에서 배운 캐시의 개념과 비슷하게 생각하였음. 참고 : ... Segment Treelazy propagationSegment Tree